Free-space management of storage-based applications is required for reusing the space freed when objects are deleted, for new objects or for new data of existing objects. Low level volume management involves handling fixed size blocks that compose the volume, which makes space allocation easier to handle. However, free-space management becomes more complicated when the managed storage consists of variable sized objects as usually happens in upper layer storage applications, such as filesystems that manage variable sized files, databases that manage tables and indexes of various sizes and the like.
Free space is managed using various types of data-structures, some of which are described below.
A file system is required to keep track of allocated and free blocks within a logical volume that contains objects of the file system. The simplest solution often used is an allocation bitmap that represents allocated and free space, wherein each bit in the bitmap represents a block in the volume and indicates whether the specific block in a volume is allocated or free. When the file system needs to allocate additional blocks, it refers to the bitmap to identify which blocks are available. However, it is extremely inefficient to search through a bitmap to find large contiguous chunks of free space, particularly when large volumes are involved.
Bitmaps of the whole volume can become quite large for high capacity volumes and need to be saved in the disk and to be read to the cache memory upon allocation change and then be written back to the disk.
Extent lists are the most common alternative to bitmaps. Extent lists are data structures that organize free space into contiguous regions described by location in storage and length of available blocks. Extent lists are sometimes preferred for compression, representing free space using less memory and storage. However, they can grow to be larger than bitmaps, particularly when storage is heavily utilized by small allocations.
One of the problems of bitmaps is de-allocation of blocks. Space allocation algorithms can control the locality of allocations, by deciding which area of the volume is currently dedicated for allocation of new data, but there is no control over the locality of frees, as portions of a file that were allocated in different times can be spread all over the volume. As an example of a worst case, removing 4 GB of object data (a million 4K blocks) could require million bitmaps (of 4K bit each) to be read, modified, and written back again.